package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/26/20 6:52 PM
 *
 *  https://leetcode-cn.com/problems/maximal-rectangle/
 */
public class _85_最大矩形 {

    public int maximalRectangle(char[][] matrix) {

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {

            return 0;
        }

        int max = 0;
        for (int i = 0; i < matrix.length; i++) {

            for (int j = 0; j < matrix[0].length; j++) {

                if (matrix[i][j] == '0') {
                    continue;
                }

                int k =  j - 1;

                for (; k >= 0 ; k--) {

                    if (matrix[i][k] == '0'){
                        break;
                    }
                }

                int l = i - 1;

                for (; l >= 0 ; l--) {

                    if (matrix[l][j] == '0') {

                        break;
                    }
                }

                int tmpMax = 1;

                for (int m = j; m > k ; m--) {


                    boolean flag = false;
                    int n = i;
                    for (; n > l ; n--) {

                        if (matrix[n][m] == '0'){

                            flag = true;
                            break;
                        }else {

                            tmpMax = Math.max(tmpMax,(j - m + 1) * (i - n + 1));
                        }
                    }

                    if (flag) {
                        l = n;
                    }
                }

                max = Math.max(max,tmpMax);
            }
        }

        return max;
    }
}
